The present invention relates to a compiling method for converting a source program including in an iterative loop such as a DO loop of FORTRAN a variable which is recurrsively defined during loop iteration into a plurality of parallelly executable object program portions.
A parallel computer having a plurality of parallelly operated processors has been being studied and developed from the old mainly by colleges and enterprises in the U.S. For such a parallel processing system, a FORTRAN type language which has been being used for a conventional serial execution type computer is frequently adopted as an input language. CRAY X-MP by CRAY Corp., multiprocessor by IBM Corp. and Alliant FX/8 by Alliant Corp. have been known. The CRAY X-MP is discussed in "A Data-Flow Approach to Multitasking on CRAY X-MP", ACM-0-89791-174-1-12/85-0/07, pp 107-114. The IBM multiprocessor is discussed in "Microtasking on IBM Multiprocessors", IBM Journal, Research and Development, Vol. 30, No. 6, November 1986, pp 574-582. The Alliant FX/8 is discussed in "The Architecture of The Alliant FX/8 Computer", CH2285-5/86/0000/0390, 1986 IEEE, pp 390-393.
In order to write a source program which runs on a parallel computer in FORTRAN language, one of the following two methods may be used. In one method, a separate program is prepared for each processor. In the other method, one program is divided by a processing system into a plurality of source program portions with processors. It has been known that the latter method imparts a lower load to a user who writes a program. When the processing system divides one FORTRAN program into each processor, a loop in the program which has a high execution rate may be parallelly executed for each repetition. ##EQU1## In such a program, the program portion (1) when I=1, the program portion (1) when I=2, . . . , the program portion (1) when I=N are parallelly executed by separate processors.
A problem which arises in this case is a variable which is recurrsively defined for each loop iteration, such as J or X in (1). This variable is called an induction variable.
In the FORTRAN source program, a frequency of the calculation defined in this manner is very high. For the conventional serial computer, a technique to improve an execution performance has been studied. For example, "Principles of Compiler Design" by A. V. Aho J. D. Ullman, pp. 466-471 discusses the induction variable elimination.
This technique is effective to a serial execution type computer but it is not effective to a parallel processing computer.
There is no reference known which discusses a method to parallelly execute the induction variable and it is supposed that one processor serially executes it or data are communicated among the processors to execute it. However, this type of processing does not improve the execution efficiency.
In a program shown in; FIGS. 8A, 8B, if DO 10 loop or DO 30 loop is parallelly executed for each predetermined number of loop repetition, the following problem arises. A statement 17 is a definition of J. For an I-th iteration of the loop, the value of J calculated in the (I-1)th iteration of the loop is used. For the parallel execution by the plurality of processors, the value of J must be transferred from the processor which executes the (I-1)th iteration to the processor which executes the I-th iteration. Accordingly, the parallel computer without communication means among the processors cannot parallelly execute, and even if it has communication means, the parallel operation is lost because of waiting time for the previous execution. In addition, a time for data communication is required. The same is true for R in a statement 18 and IA in a statement 24. The recurrsive definition which defines a new value by using the immediately previously defined value is a big factor of lowering the execution efficiency in the parallel processing as opposed to the serial processing.